A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
The present invention relates to fast packet communication systems and more particularly to asynchronous transfer mode (ATM) switches in communication networks.
Network communication systems interconnect many users in a network. Each user is connected to the network at a port. The network is formed by the interconnection of many nodes where information input at an input port from one user at a source is passed from node to node through the network to an output port and to another user at a destination. The information transferred from source to destination is packetized and each node switches incoming packets at incoming ports to outgoing packets at outgoing ports. For ATM networks, the packets are further divided into cells.
Fast packet switches may transfer hundreds of thousands of packets per second at every switch port. Each switch port is typically designed to transfer information at a rate from 50 Mbits/s to 600 Mbit/s for a broadband integrated service digital network (ISDN). Switch sizes range from a few ports to thousands of ports.
The term "fast packet switch" includes switches capable of handling both variable length packets and fixed length packets. Fixed-length packets are desirable since they simplify the switch design. Fast packet switches using short, fixed-length packets (cells) are referred to as asynchronous transfer mode (ATM) switches. Fast packet switches handle different types of communications services in a single integrated network where such services may include voice, video and data communications. Since voice and video services can tolerate only a limited amount of delay and delay variance through a network, ATM switches are suitable for such services. The ATM standard for broadband ISDN networks defines a cell having a length of 53 bytes with a header of 5 bytes and data of 48 bytes.
In a typical ATM switch, the cell processing functions are performed within the nodes of a network. Each node is an ATM switch which includes input controllers (IC's) , a switch fabric (SF), output controllers (OC's) and a node control (C). The node control is used for functions including connection establishment and release, bandwidth reservation, congestion control, maintenance and network management.
In each switch, the input controllers are typically synchronized so that all cells from input controllers arrive at the switch fabric at the same time and so that cells can be accepted or rejected according to their priority. The traffic through the switch fabric is slotted and the switch fabric delay equals the sum of the timeslot duration, pipeline delay, and the queuing delay.
The node control communicates with the input controllers and the output controllers either by a direct communication path which by-passes the switch fabric or via control cells transmitted through the switch fabric.
External connections to the switch are generally bi-directional. Bidirectional connections are formed by grouping an input controller (IC) and an output controller (OC) together to form a port controller (PC).
The input sequence of cells in a virtual channel is preserved across the switch fabric so that the output sequence of cells on each virtual channel is the same as the input sequence. Cells contain a virtual channel identifier VCI in the cell header which identifies the connection to which the cell belongs. Each incoming VCI identifier in the header of each cell is translated in an input controller to specify the outgoing VCI identifier. This translation is performed in the input controller typically by table look-up using the incoming VCI identifier to address a connection table. This connection table also contains a routing field to specify the output port of the switch fabric to which the connection is routed. Other information may be included in the connection table on a per connection basis such as the priority, class of service, and traffic type of the connection.
In an ATM switch, cell arrivals are not scheduled. In a typical operation, a number of cells may arrive simultaneously at different input ports each requesting the same output port. Operations in which requests exceeding the output capacity of the output port are referred to as output contention (or conflict). Since an output port can only transmit a fixed number (for example, one) cell at a time, only the fixed number of cells can be accepted for transmission so that any other cells routed to that port must either be discarded or must be buffered in a queue.
Different methods are employed for routing cells through a switch module, for example, self-routing and label routing.
A self-routing network operates with an input controller prefixing a routing tag to every cell. Typically, the input controller uses a table lookup from a routing table to obtain the routing tag. The routing tag specifies the output port to which the cell is to be delivered. Each switching element is able to make a fast routing decision by inspecting the routing tag. The self-routing network ensures that each cell will arrive at the required destination regardless of the switch port at which it enters.
A label routing network operates with a label in each cell referencing translation tables in each switching element. The label is translated in each switching element and hence any arbitrary network of switching elements may be employed.
Switches have two principal designs, time-division and space division. In a time-division switch fabric, all cells flow through a single communication channel shared in common by all input and output ports. In a space division switch, a plurality of paths are provided between the input and output ports. These paths operate concurrently so that many cells may be transmitted across the switch fabric at the same time. The total capacity of the switch fabric is thus the product of the bandwidth of each path and the average number of paths that can transmit a cell concurrently.
When the traffic load exceeds the available system resources in a network, congestion is present and performance degrades. When the number of cells is within the carrying capacity of the network, all cells can be delivered so that the number of cells delivered equals the number of cells sent without congestion. However, if cell traffic is increased to the level that nodes cannot handle the traffic, congestion results.
Congestion can be brought about by several factors. If nodes in a network are too slow to perform the various tasks required of them (queuing buffers, updating tables, etc.), queues build up, even though excess line capacity exists. On the other hand, even if nodes are infinitely fast, queues will build up whenever the input traffic rate exceeds the capacity of the output traffic rate for any particular group of outputs.
If a node has no free buffers for queuing cells, the node must discard newly arriving cells. For packet data traffic, when a cell is discarded, the packet from which the discarded cell came will be retransmitted, perhaps many times, further aggravating the congestion.
A difference exists between congestion control and flow control. Congestion control relates to insuring that each part of the network is able to carry the offered traffic. Congestion control is a network-wide consideration involving the behavior and carrying capacity of each part of the network at the time that traffic is offered to each part of the network.
Flow control, in contrast, relates to the point-to-point traffic between a given source and a given destination. Flow control insures that a source does not continually transmit data faster than the destination can receive it. Flow control generally involves direct feedback from the destination to the source to signal the source as to the availability of the destination to receive transmissions from the source.
ATM WAN's And LAN's. Over the last few years, the physical topology of local area networks has migrated from the ring and the multidrop bus toward a star configuration--the hub. A star topology is easier to manage and offers higher reliability. However, the technology remains shared medium, resulting in the "LAN-in-a-box". As the power of the desktop workstation increases, the capacity of the LAN must increase in proportion. Shared medium access in the Gb/s region is significantly more expensive than access in the 100 Mb/s range. Thus pressure is mounting for the high-performance LAN hub to abandon its internal shared medium architecture and adopt a switched architecture.
In addition to the requirement for increasing local area bandwidth is the desire to support multimedia applications. These will require the integration of video, voice, image, and data traffic. There is also a significant requirement to achieve closer interworking between local area and wide area networks. ATM has been proposed as a technology capable of offering high capacity switching and supporting multiservice traffic. It has received much attention in the public wide area network as the future broadband integrated services digital network (B-ISDN). ATM is therefore a clear candidate for the high-performance LAN and campus backbone network.
Traffic Management in an ATM LAN. In a shared medium LAN, be it ting, bus, or backplane, all of the attached stations share a single resource--the shared medium. To transmit, a station contends for access to the shared medium via the medium access (MAC) protocol. If the network is heavily loaded, it will apply backpressure, through the MAC protocol, to stations requesting access. Once a station has successfully gained access to the shared medium, it may transmit its data without fear of causing network congestion since all stations can receive at the data rate of the shared medium. But the bandwidth of the shared medium has now become a bottleneck. In seeking a switched solution, the shared medium is replaced by a switch fabric of greater aggregate capacity than any individual input or output port. In so doing, the MAC protocol is removed, removed the backpressure that the MAC protocol provides is removed, and the network is opened up to the possibility of congestion if too much traffic is directed at any single output port over a short time interval.
A number of schemes have been proposed for traffic management in an ATM network. The most frequently discussed approach is to determine the traffic characteristics of the source and to allocate resources accordingly when the call is admitted to the network. This approach is best suited to traffic sources that can be accurately characterized in advance of transmission, for example, voice and compressed video. Individual data sources are very difficult to characterize in this manner. If a service with the characteristics of a LAN are to be provided, then, at least for data traffic, each source must be permitted to burst at high speed and dynamically share the available capacity between active sources.
Within a LAN or campus network based upon ATM, the propagation delay across the network is low so a simple feedback scheme between the point of congestion and the source may be employed to replace the backpressure mechanism that the MAC protocol provided in a shared medium LAN. Traffic sources with well defined characteristics may be handled by call admission and bandwidth reservation. Such traffic is transmitted at a higher delay priority and is not subject to the backpressure mechanism. The remaining bandwidth is then available to be shared dynamically between those sources that require a LAN-like (best-effort) service. Sources that require this service must be subject to the backpressure mechanism in the same way that sources must conform to the MAC protocol if they wish to attach to a LAN.
Packet Congestion Control Algorithms. Congestion control algorithms for packet switches have included preallocating resources, packet discarding, packet restricting, flow control, and input choking.
The preallocating of resources avoids a congestion problem for virtual channels. When a virtual channel is set up, a call request travels through the network making table entries at each node that control the route to be followed by subsequent traffic. With preallocating, each call request reserves one or more data buffers in each node unless all the buffers are already reserved. If all buffers are reserved, another route is found or a "busy signal" is returned to the source. If buffers are reserved for each virtual channel in each node, there is always a place to store any incoming packet to that node. The problem with preallocation is that substantial buffer resources are allocated to specific virtual channel connections, whether or not there is any traffic over the virtual channel. An inefficient use of resources results because resources not being used by the connection to which they are allocated are nevertheless unavailable to other virtual channels.
With packet discarding, if a packet arrives at a node and there is no place to store it, the node discards it. Congestion is resolved by discarding packets at will. A copy of the packet is kept elsewhere and retransmitted later. Discarding packets at will, if carried too far, results in inefficient operation since the retransmission tends to increase traffic in an already congested network.
Packet restricting limits the number of packets at any location in a network to avoid congestion since congestion only occurs when there is an excessive number of packets at a particular location in the network. Packet restricting is performed in one method by issuing permits. Whenever a node requests sending a packet, the node must first obtain a permit. When the destination finally receives the packet, the permit is again made available for reuse. Although the permit method guarantees that the network as a whole will never become congested, it does not guarantee that a given node will not become swamped with packets. Also, the permit distribution mechanism is difficult to implement without suffering long delays.
Flow control has been used in some networks (for example, ARPANET) in an attempt to eliminate isolated congestion. For example, flow control has been used by the transport layer to keep one host from saturating another host and by one node to prevent that node from saturating its neighbor node. However, flow control has not been effective to solve network-wide congestion.
Input choking has been used to control congestion. Whenever congestion is detected, a choke packet is sent back to the source to choke off input packets. To determine congestion, each newly arriving packet at a node is checked to see if its output line is congested. When congestion is detected at a node, the node sends a choke packet back to the source identifying the destination having congestion. When a source receives a choke packet, the source reduces by some factor the traffic sent to the specified destination. Other packets having the same destination that are already under way generate additional choke packets that are ignored by the source for a first time period. After that first time period has expired, the source looks for more choke packets for a second time period. If during the second time period a choke packet arrives indicating that the line is still congested, the source reduces the flow still more and repeats the process. If no choke packets arrive during a subsequent second time period, the source increases the flow again. The feedback in this protocol tends to prevent congestion but does not throttle flow until congestion is detected.
Several variations on the input choking algorithm have been proposed for packet switches. In one variation, the nodes maintain two congestion thresholds. Above the first threshold but below the second, choke packets are sent back. Above the second threshold, incoming traffic is discarded, it being assumed by the second threshold that the host has received notification of the congestion.
Another input choking variation is to use queue lengths instead of line utilization as the trigger signal for congestion. Another choking variation has nodes propagate congestion information along with routing information, so that the congestion trigger is not based on information from only one node, but on information that somewhere along the path there is congestion. By propagating congestion information in the network, choke packets can be sent at an early time, before too many more packets are under way, thus preventing congestion from building up.